import java.util.*;

/**
 * 面试题06：从尾到头打印链表
 */
public class Offer_06 {
    /**
     * 方法二：栈
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        int size = stack.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = stack.pop();
        }
        return ans;
    }

    List<Integer> list = new ArrayList<>();

    /**
     * 方法一：递归
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int[] reversePrint1(ListNode head) {
        recur(head);
        int size = list.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    public void recur(ListNode node) {
        if (node == null) {
            return;
        }
        recur(node.next);
        list.add(node.val);
    }

    public static void main(String[] args) {
        Offer_06 solution = new Offer_06();

        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int[] ans = solution.reversePrint(head);
        System.out.println(Arrays.toString(ans));
    }
}
